package com.ma.DataStruct.trietree;

import java.util.ArrayList;
import java.util.List;

/*
 * 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。
 * 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
 *
 * 实现 MagicDictionary 类：
 *      MagicDictionary() 初始化对象
 *      void buildDict(String[]dictionary) 使用字符串数组dictionary 设定该数据结构，dictionary 中的字符串互不相同
 *      bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
 */
public class Solution676 {
    public static void main(String[] args) {
        MagicDictionary magicDictionary = new MagicDictionary();
        String[] words = {"hello", "leetcode"};
        magicDictionary.buildDict(words);
        System.out.println(magicDictionary.search("hello")); // 返回 False
        System.out.println(magicDictionary.search("hhllo")); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
        System.out.println(magicDictionary.search("hell")); // 返回 False
        System.out.println(magicDictionary.search("leetcoded")); // 返回 False

    }
}

class MagicDictionary {
    List<String>[] lists;

    public MagicDictionary() {
        this.lists = new ArrayList[100];
    }

    public void buildDict(String[] dictionary) {
        // 根据单词长度构建集合
        for (String word : dictionary) {
            int index = word.length() - 1;
            if (lists[index] == null) {
                lists[index] = new ArrayList<>();
            }
            lists[index].add(word);
        }

    }

    public boolean search(String searchWord) {
        int index = searchWord.length() - 1;
        //该长度的单词集合为空，直接返回false
        if (lists[index] == null) {
            return false;
        }
        for (String word : lists[index]) {
            if (valid(word, searchWord, index)) {
                return true;
            }
        }
        return false;

    }

    private boolean valid(String word, String searchWord, int index) {
        int num = 0;
        for (int i = 0; i <= index; i++) {
            if(word.charAt(i)!=searchWord.charAt(i)) {
                if(++num>1){
                    return false;
                }
            }
        }
        return num==1;

    }
}
